﻿<!DOCTYPE html>
<html>
<head>
    <title>八数码</title>
    <script src="../common.js"></script>
    <style>
        body {
            text-align: center;
            width: 500px;
            margin: auto;
        }

        div.top {
            text-align: center;
            padding: 20px;
        }

        div.title {
            font-size: 40px;
        }

        div.ctol {
            font-size: 12px;
        }

        div.ctl {
            top: 250px;
            width: 500px;
            background: #ccc;
            margin: auto;
            position: absolute;
            padding: 20PX 0;
            z-index: 10;
            color: #f00;
            font-size: 40px;
            display: none;
        }
    </style>
</head>
<body style='text-align:center'>
    <div class="top">
        <div class="title">八数码</div>
        <div class="ctol">
            用较少的步骤移动数字格子，达到目标状态
            <br />
            <button id="reset">重置本关</button>
            <button id="auto">自动求解</button>
        </div>
    </div>
    <canvas id="area" width="300" height="451"></canvas>
    <div id="ctl" class="ctl">
        <label id="info"></label>
        <div>
            <button id="new">再来一局</button>
        </div>
    </div>
    <script type="text/javascript">
        //var fac = [1, 1, 2, 6, 24, 120, 720, 5040, 40320]; //i的阶乘为fac[i]
        //// 康托展开-> 表示数字a是 a的全排列中从小到大排，排第几
        //// n表示1~n个数  a数组表示数字。
        //function kangtuo(n, a) {
        //    var i, j, t, sum;
        //    sum = 0;
        //    for (i = 0; i < n ; ++i) {
        //        t = 0;
        //        for (j = i + 1; j < n; ++j)
        //            if (a[i] > a[j])
        //                ++t;
        //        sum += t * fac[n - i - 1];
        //    }
        //    return sum + 1;
        //}
        //function reverse_kangtuo(n, k) {
        //    var i, j, t, vst = {};
        //    var s = "";
        //    --k;
        //    for (i = 0; i < n; i++) {
        //        t = k / fac[n - i - 1];
        //        for (j = 1; j <= n; j++)
        //            if (!vst[j]) {
        //                if (t === 0) break;
        //                --t;
        //            }
        //        s += j;
        //        vst[j] = 1;
        //        k %= fac[n - i - 1];
        //    }
        //}

        function Game() {
            var finishes = [
                [1, 2, 3, 4, 5, 6, 7, 8, 0],
                [0, 1, 2, 3, 4, 5, 6, 7, 8],
                [0, 8, 7, 6, 5, 4, 3, 2, 1],
                [8, 7, 6, 5, 4, 3, 2, 1, 0],
                [1, 2, 3, 8, 0, 4, 7, 6, 5]
            ];
            this.new = function () {
                //this.finish = [8, 7, 6, 5, 4, 3, 2, 1, 0];
                //this.start = [5, 8, 0, 7, 3, 6, 2, 4, 1];
                var f = parseInt(Math.random() * finishes.length);
                this.finish = finishes[f];
                this.start = Array.apply(null, this.finish);
                this.init();
                var s, e;
                for (var i = 0, em = 0; i < this.start.length * 2 || (i - em) % 2 === 1; i++) {
                    s = parseInt(Math.random() * (this.start.length - 1));
                    if (i % 2 === 0) {
                        e = s + 3;
                        if (e > 8) {
                            e -= 6;
                        }
                    } else {
                        e = s + 1;
                        if (e % 3 === 0) {
                            e -= 2;
                        }
                    }
                    if (this.start[s] * this.start[e] === 0) {
                        em--;
                    } //else {
                    var t = this.start[s];
                    this.start[s] = this.start[e];
                    this.start[e] = t;
                    //}
                }
                this.init();
                window.console.log(this.finish.join(""));
                window.console.log(this.start.join(""));
                //this.a = this.start.join("");
            }

            this.init = function () {
                this.state = 0;
                this.current = this.start;
                this.ep = this.current.indexOf(0);
                this.ex = this.ep % 3;
                this.ey = parseInt(this.ep / 3);
            }

            this.move = function (cp, callback) {
                if (this.state) {
                    return false;
                }
                var p = this.current[cp];
                if (p === 0) {
                    return false;
                }
                var cx = cp % 3;
                var cy = parseInt(cp / 3);
                if ((cx === this.ex && Math.abs(cy - this.ey) === 1) ||
                    (cy === this.ey && Math.abs(cx - this.ex) === 1)) {
                    var c = Array.apply(null, this.current);
                    c[this.ep] = p;
                    c[cp] = 0;
                    typeof callback === "function" && callback(p, cp, this.ep);
                    this.ep = cp;
                    this.ex = cx;
                    this.ey = cy;
                    this.current = c;
                    if (this.check()) {
                        this.state = 1;
                    }
                    //this.a = this.current.join("");
                    return true;
                }
                return false;
            }

            this.check = function () {
                for (var i = 0; i < this.finish.length; i++) {
                    if (this.finish[i] !== this.current[i]) {
                        return false;
                    }
                }
                return true;
            }
        }

        var w = h = 3;
        var cw = 99;
        var game = new Game();
        game.new();
        var area = $("area");
        var ctx = area.getContext("2d");
        ctx.lineWidth = 1;
        var fill = function (x, y, n) {
            ctx.font = "50px serif";
            ctx.fillStyle = n ? "#F60" : "#09F";
            var rx = x * cw + 0.5;
            var ry = y * cw + 0.5;
            ctx.fillRect(rx + 1, ry + 1, cw - 2, cw - 2);
            if (n) {
                ctx.fillStyle = "#FFF";
                ctx.fillText(n + "", rx + 39, ry + 65);
            }
        }
        var fillo = function (ox, oy, x, y, n) {
            ctx.font = "20px serif";
            ctx.fillStyle = n ? "#F60" : "#09F";
            var rx = x * cw / 3 + 0.5;
            var ry = y * cw / 3 + 0.5;
            ctx.fillRect(rx + 1 + ox, ry + 1 + oy, cw / 3 - 2, cw / 3 - 2);
            if (n) {
                ctx.fillStyle = "#FFF";
                ctx.fillText(n + "", rx + 12 + ox, ry + 22 + oy);
            }
        }
        var paint = function () {
            ctx.clearRect(0, 0, 301, 451);
            var i;
            var ox = cw, oy = cw * 3 + 36, ow = parseInt(cw / 3);
            for (i = 0; i <= w; i++) {
                ctx.moveTo(i * cw + 0.5, 0);
                ctx.lineTo(i * cw + 0.5, h * cw);
                ctx.stroke();
                ctx.moveTo(i * ow + 0.5 + ox, oy);
                ctx.lineTo(i * ow + 0.5 + ox, h * ow + oy);
                ctx.stroke();
            }
            for (i = 0; i <= h; i++) {
                ctx.moveTo(0, i * cw + 0.5);
                ctx.lineTo(w * cw, i * cw + 0.5);
                ctx.stroke();
                ctx.moveTo(ox, i * ow + 0.5 + oy);
                ctx.lineTo(w * ow + ox, i * ow + 0.5 + oy);
                ctx.stroke();
            }

            for (var y = 0; y < h; y++) {
                for (var x = 0; x < w; x++) {
                    fill(x, y, game.start[y * 3 + x]);
                }
            }
            ctx.font = "20px serif";
            ctx.fillStyle = "#F00";
            ctx.fillText("目标状态", 110, 330);

            for (var y = 0; y < h; y++) {
                for (var x = 0; x < w; x++) {
                    fillo(ox, oy, x, y, game.finish[y * 3 + x]);
                }
            }

            $("ctl").style.display = "none";
        }
        var move = function (n, cp, ep) {
            var cx = cp % 3;
            var cy = parseInt(cp / 3);
            fill(cx, cy, 0);

            var ex = ep % 3;
            var ey = parseInt(ep / 3);
            fill(ex, ey, n);
        }
        area.onclick = function (e) {
            if (game.auting || game.state) {
                return;
            }
            if (e.layerX % cw === 0 || e.layerY % cw === 0) {
                return;
            }
            var x = parseInt(e.layerX / cw);
            var y = parseInt(e.layerY / cw);
            var id = y * w + x;
            if (game.move(id, move)) {
                if (game.state) {
                    $("info").innerHTML = "恭喜你完成了游戏";
                    $("ctl").style.display = "block";
                }
            }
        }

        paint();

        $("new").onclick = function (e) {
            game.new();
            paint();
        }

        $("reset").onclick = function (e) {
            game.init();
            paint();
        }

        $("auto").onclick = function (e) {
            game.init();
            paint();
            var auto = new Auto();
            var path = auto.solve(game);
            if (path) {
                var si = window.setInterval(function () {
                    var p = path.shift();
                    if (p != null) {
                        game.move(p, move);
                    } else {
                        window.clearInterval(si);
                    }
                }, 200);
            } else {
                window.alert("无解");
            }
        }

        function Auto() {
            this.solve = function (game) {
                var states = [game.start.join("")];
                var games = [game];
                var deep = 0;
                var queues = [];
                while (true) {
                    if (games.length === 0) {
                        window.console.log("搜索深度：" + deep);
                        window.console.log("队列轨迹：" + queues.join());
                        window.console.log("队列峰值：" + Math.max(...queues));
                        window.console.log("搜索状态数：" + states.length);
                        return null;
                    }
                    deep++;
                    queues.push(games.length);
                    var newGames = [];
                    for (var k = 0; k < games.length; k++) {
                        var cg = games[k];
                        var g = null;
                        for (var i = 0; i < cg.current.length; i++) {
                            var p = cg.current[i];
                            if (p === 0) {
                                continue;
                            }
                            if (g == null) {
                                g = new Game();
                                g.finish = game.finish;
                                g.start = cg.current;
                                g.init();
                            }
                            if (g.move(i)) {
                                var state = g.current.join("");
                                if (states.indexOf(state) === -1) {
                                    g.path = i;
                                    g.last = cg;
                                    //window.console.log(state);
                                    if (g.check()) {
                                        var tg = g;
                                        var path = [];
                                        while (tg && tg.path != null) {
                                            path.unshift(tg.path);
                                            tg = tg.last;
                                        }
                                        window.console.log("搜索深度：" + deep);
                                        window.console.log("队列轨迹：" + queues.join());
                                        window.console.log("队列峰值：" + Math.max(...queues));
                                        window.console.log("搜索状态数：" + states.length);
                                        return path;
                                    }
                                    states.push(state);
                                    newGames.push(g);
                                }
                                g = null;
                            }
                        }
                    }
                    games = newGames;
                }
            }
        }
    </script>
</body>
</html>
